from typing import *


class Solution:

    def maxStudents(self, seats: List[List[str]]) -> int:
        m, n = len(seats), len(seats[0])
        r = 1 << n
        limit = r - 1

        u = []  # r 范围内，01间隔的数字，即可能的坐人情况
        for i in range(r):
            j, b = 3, True  # b两个人挨着的时候是11
            for _ in range(n - 1):
                if i & j == j:  # 存在两人挨着，不行
                    b = False
                    break
                j <<= 1
            if b:  # 不存在两人挨着，行
                u.append(i)

        s = []  # 排除坏椅子，可以坐人的状态
        for i in range(m):
            c = 0
            for j in range(n):
                if seats[i][j] == '.':
                    c |= 1 << j
            s.append(c)

        f = [[0] * r for _ in range(m + 1)]
        for i in range(1, m + 1):  # 第i排
            for j in u:  # 枚举这一排每种坐人情况
                if j & s[i - 1] == j:  # 第i排确实可以这么坐
                    last = limit & (j << 1 | j >> 1)  # 上一排不能出现人的位置
                    for k in u:  # 枚举上一排
                        if last & k == 0:  # 上一排坐人情况是k时，与不能坐人无交集，说明上一排k对于这排j是有效坐人情况
                            f[i][j] = max(f[i][j], j.bit_count() + f[i - 1][k])
        return max(f[m])


s = Solution()
print(
    s.maxStudents([["#", ".", "#", "#", ".", "#"],
                   [".", "#", "#", "#", "#", "."],
                   ["#", ".", "#", "#", ".", "#"]]))
